package org.example;

/**
 * 删除链表的倒数第N个节点
 */
public class Solution29 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点，方便操作
        ListNode dummy  = new ListNode(0);
        dummy.next = head;

        // 初始化两个指针
        ListNode first = dummy;
        ListNode second = dummy;

        // 让第一个指针先走n步
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // 同时移动两个指针，直到第一个指针到达链表末尾
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 删除倒数第n个节点
        second.next = second.next.next;

        // 返回新的头节点
        return dummy.next;
    }

}
